Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

题目大意：给定一个有序链表，将其转化成平衡二叉搜索树

题目难度：Medium

/**
 * Created by gzdaijie on 16/6/8
 * slow每次走一步,fast每次走2步,那么fast走完,slow恰好走到中点
 * pre记录slow的前一个节点,pre.next = null,可以拆分链表
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;

        ListNode pre = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode node = new TreeNode(slow.val);

        if (pre == null) return node;
        pre.next = null;
        node.left = sortedListToBST(head);
        node.right = sortedListToBST(slow.next);
        return node;
    }
}